unit LimitedStack;

{
  @Name:
  LimitedStack

  @Description:
  This unit provides a limited stack implementation. A stack is a list
  that works at a system of "Last In, First Out". A limited stack is a
  stack that accepts only a limited amount of elements. If you add one
  more element than the limit, the first element (the element that is
  in the stack the longest) will be deleted from the stack.

  @Author:
  Hans De Mulder

  @Website:
  http://www.sxdev.be/

  @License:
  GNU General Public License v3 (http://www.gnu.org/licenses/gpl-3.0.html)

  @Version:
  1.1.0

  @Changelog:
    v1.0.0
      Initial release
    v1.1.0
      Reformed dynamic arrays, using now pointers
}

{ -------------------- INTERFACE -------------------- }
interface

uses
  SysUtils, Classes;

const
  MIN_ELEMENTS = 1;

type
  TStackArray = array of TObject;

  TStackPointer = ^TStackRecord;

  TStackRecord = record
    element: TObject;
    previous: TStackPointer;
    next: TStackPointer;
  end;

  TLimitedStack = class(TObject)
    public
      constructor Create(maxElements: Integer); overload;
      destructor Destroy(); overload;
      function GetCurrentAmount(): Integer;
      procedure Add(element: TObject);
      function Retrieve(var element: TObject): Boolean;
      function GetLastElement(var element: TObject): Boolean;
      procedure GetStack(var outStack: TStackArray);
    private
      currentAmount: Integer;
      maxAmount: Integer;
      stack: TStackPointer;
      firstMem: TStackPointer;
      lastStackElement: TStackPointer;
  end;


  LimitedStackException = class(Exception);

{ -------------------- IMPLEMENTATION -------------------- }
implementation

constructor TLimitedStack.Create(maxElements: Integer);
begin
  inherited Create;

  if (maxElements >= MIN_ELEMENTS) then
    begin
      maxAmount := maxElements;
      currentAmount := 0;
      lastStackElement := nil;

      GetMem(firstMem, maxAmount * SizeOf(TStackRecord));
      stack := firstMem;
    end
  else
    begin
      raise LimitedStackException.Create('The stack has to have a limit of at least ' + IntToStr(MIN_ELEMENTS) + '.');
    end;
end;


destructor TLimitedStack.Destroy();
var
  element: TObject;
begin
  while (stack <> nil) do
    begin
      element := stack^.element;
      stack := stack^.previous;
      element.Free;
    end;

  FreeMem(stack);

  inherited Destroy;
end;


function TLimitedStack.GetCurrentAmount(): Integer;
begin
  Result := currentAmount;
end;


procedure TLimitedStack.Add(element: TObject);
var
  tempStackPointer: TStackPointer;
begin
  if (currentAmount = maxAmount) then
    begin
      tempStackPointer := lastStackElement;
      lastStackElement := tempStackPointer^.previous;
      tempStackPointer^.element.Free;
    end;

  tempStackPointer := nil;
  New(tempStackPointer);

  tempStackPointer^.element := element;
  tempStackPointer^.next := stack;
  tempStackPointer^.previous := nil;
  stack^.previous := tempStackPointer;

  if (currentAmount = 0) then
    lastStackElement := tempStackPointer;

  stack := tempStackPointer;
  currentAmount := currentAmount + 1;
end;


function TLimitedStack.Retrieve(var element: TObject): Boolean;
begin
  if ((currentAmount = 0) or (stack = nil)) then
    begin
      element := nil;
      Result := false;
    end
  else
    begin
      element := stack^.element;
      stack := stack^.next;
      currentAmount := currentAmount - 1;

      if (currentAmount = 0) then
        stack := firstMem;

      Result := true;
    end;
end;


function TLimitedStack.GetLastElement(var element: TObject): Boolean;
begin
  if ((currentAmount = 0) or (stack = nil)) then
    begin
      element := nil;
      Result := false;
    end
  else
    begin
      element := stack^.element;
      Result := true;
    end;
end;

{ For debugging only }
  procedure TLimitedStack.GetStack(var outStack: TStackArray);
  var
    element: TObject;
    pointer: TStackPointer;
    i: Integer;
  begin
    SetLength(outStack, currentAmount);
    pointer := stack;
    for i := 0 to currentAmount - 1 do
      begin
        outStack[i] := pointer^.element;
        pointer := pointer^.next;
      end;
  end;


end.
